package main

import (
	"container/list"
	"fmt"
	"math"
)

//超时
func maxSubarraySumCircular(nums []int) int {
	res := nums[0]
	for i, _ := range nums {
		maxSum := oneMaxSubarraySumCircular(nums, i)
		if maxSum > res {
			res = maxSum
		}
	}
	return res
}

func oneMaxSubarraySumCircular(nums []int, index int) int {
	n := len(nums)
	sum := nums[index]
	maxSum := sum

	for i := 1; i < n; i++ {
		nextNum := nums[(index+i)%n]
		sum += nextNum
		if sum > maxSum {
			maxSum = sum
		}
	}
	return maxSum
}

/*
100ms 击败 8.60%使用 Go 的用户
*/

//前缀和+单调队列
func maxSubarraySumCircular2(nums []int) int {
	n := len(nums)
	//将原数组循环一遍放到dualNums
	dualNums := make([]int, 2*n-1)
	preSums := make([]int, 2*n-1)

	for i := 0; i < len(dualNums); i++ {
		dualNums[i] = nums[i%n]
	}
	//dualNums前缀和数组
	preSums[0] = dualNums[0]
	for i := 1; i < len(dualNums); i++ {
		preSums[i] = preSums[i-1] + dualNums[i]
	}

	//res默认值，可能是最大的某个数
	res := nums[0]
	for _, num := range nums {
		if num > res {
			res = num
		}
	}
	h := help(preSums, n)
	return int(math.Max(float64(h), float64(res)))
}

type G struct {
	val   int
	index int
}

func help(nums []int, limit int) int {
	//单调栈  3 2 1 4 6 5
	deque := list.New()
	res := math.MinInt32
	for i, num := range nums {
		if deque.Len() == 0 {
			deque.PushBack(G{num, i})
			continue
		}
		//保持单调递增
		l := deque.Front().Value.(G)
		for deque.Len() > 0 && deque.Back().Value.(G).val >= num {
			deque.Remove(deque.Back())
		}
		//保持队列最左最右的index只差不超过limit+1
		if i-l.index <= limit {
			//新元素入队
			deque.PushBack(G{num, i})
			if num-l.val > res {
				res = num - l.val
			}
		} else {
			for deque.Len() > 0 && i-deque.Front().Value.(G).index > limit {
				deque.Remove(deque.Front())
			}
			//新元素入队
			deque.PushBack(G{num, i})
			if num-deque.Front().Value.(G).val > res {
				res = num - deque.Front().Value.(G).val
			}
		}

	}
	return res
}

//最大子数组和
func maxSubarraySum(nums []int) int {
	n := len(nums)
	//dp[r]表示以nums[r]为子数组最后一个元素时，子数组最大和的值
	dp := make([]int, n)
	dp[0] = nums[0]
	for i := 1; i < n; i++ {
		if dp[i-1]+nums[i] > nums[i] {
			dp[i] = dp[i-1] + nums[i]
		} else {
			dp[i] = nums[i]
		}
	}

	res := nums[0]
	for _, s := range dp {
		if s > res {
			res = s
		}
	}
	return res
}

func main() {
	//nums := []int{3,1,3,2,6}
	//nums := []int{5,-3,5}
	nums := []int{6, 9, -3}
	fmt.Println(maxSubarraySumCircular2(nums))

	//nums = []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	//fmt.Println(maxSubarraySum(nums))
}
